package 链表和树.二叉树;
//Java：二叉搜索树中第 K 小的元素
public class KthSmallestElementInABst{
    public static void main(String[] args) {
        Solution solution = new KthSmallestElementInABst().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
class Solution {
        //注意题目是二叉搜索树，如果中序遍历的话就是从小到大所以遍历到第k个节点值就是答案

    //写法一：记录答案
    private int ans;
    private int k;

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }
    private void dfs(TreeNode node) {
        if(node == null || k == 0){// // 当k为0时，不再继续遍历再右侧体现就是5节点准备遍历6的时候判断到k=0跳出递归
            return;
        }

        dfs(node.left);//左
        if(--k == 0){
            ans = node.val;//根  //注意这里不是返回的时候还有很多上层调用
        }

        dfs(node.right);//右子树
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}